Sorting is the process of arranging items in an "order". The entities of interest are records each having an associated key value. The sorting objective is to determine a permutation of records which puts the keys in a non-decreasing order. A sorting activity is characterized by the manner by which the rearrangement is accomplished, as well as whether it may be accomplished in its entirety within the internal memory local to the CPU executing the sort, that is, where the data neatly fits into the random access internal (main) memory of a CPU.
A "distribution sort" separates records into contiguous ranges so that all records in one range have keys that are less in value than the keys of the records in the next range. On the other hand, a "merge sort" combines two or more linearly ordered lists such that the combined list is also linearly ordered. Typically, a two-way merge sort compares pairs of items and puts each pair in order, then merges pairs so that the resulting quadruples are in order, then merges quadruples into sorted octuples, and so on, until there are no more merges possible.
An "external sort" refers to sorting techniques applicable to files of data that exceed the capacity of primary or internal memory and rely upon secondary storage, such as DASD, tapes and drums during the sorting process. In merge sort, which is one type of external sorting, parts of a file are read into internal memory, ordered internally, and then rewritten on external devices or secondary storage. One technique, "replacement-selection", produces an intermediate file containing one or more ordered lists (strings) from the unordered "input file". Replacement-selection produces ordered strings of varying lengths, the average length being double the capacity of internal memory. Reference should be made to E. F. Moore, U.S. Pat. No. 2,983,904, 1961. The strings can optimally be merged into one ordered string by forming a "minimal merge Huffman tree". The minimal merge trees are constructs with terminal nodes representing string lengths and arranged so that the value of the merge tree is as small as possible.
Most external sorting methods used for data stored on disk drives are merge based. As suggested, these require the generation of several initial sorted strings using replacement-selection and then repeatedly merging the string until only one string remains. Whitlow et al, U.S. Pat. No. 4,210,961, "Sorting System", issued July 1, 1980, described a classical merge-based external sorting method.
On the other hand, associative memory devices have been used in both sorting and searching applications. Chang et al, "Associative Search Bubble Devices for Content Addressable Memories", 18 IBM Technical Disclosure Bulletin, pp. 598-602, July 1975, described magnetic bubble memory devices both as a word and serial by bit content addressable memory. Also, Belser, U.S. Pat. No. 4,168,535, "Non-volatile Bubble Domain Memory System", issued Sept. 18, 1979, depicts state-of-the-art multiple minor/major loop bit storage arrays. Likewise, Doty et al, "Magnetic Bubble Memory Architectures for Supporting Associative Searching of Relational Databases", 29 IEEE Transactions on Computers, pp. 957-970, Nov. 1980, substantially extended a parallel architecture of magnetic bubble memories to support associative searching in relational databases. C. S. Lin, "Sorting With Associative Secondary Storage Devices", Proceedings of AFIPS, National Computer Conference, 1977, pp. 691-695, described a computer implementable method for executing a distribution sort using a histogram of keys and associative searching on a head-per-track disk. Lin is operable only when key values are evenly distributed.